package com.example.hot100;

import java.util.*;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 *
 *  示例 1:
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 *
 *  示例 2:
 * 输入: nums = [1], k = 1
 * 输出: [1]
 */
public class Leetcode347_TopKFrequent {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        int[] res = new Solution().topKFrequent(nums, k);
        System.out.println(Arrays.toString(res));
    }

    static class Solution {
        /**
         * 解法二:HashMap + 桶排序
         *
         * @param nums
         * @param k
         * @return
         */
        public int[] topKFrequent2(int[] nums, int k) {
            List<Integer> resList = new ArrayList<>();
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                int value = map.getOrDefault(num, 0);
                map.put(num, ++value);
            }

            //桶排序
            //将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标
            List<Integer>[] lists = new List[nums.length + 1];

            map.forEach((key, value) -> {
                if (lists[value] == null) {
                    lists[value] = new ArrayList<>();
                }
                lists[value].add(key);
            });
            int i = nums.length;
            while (k > 0 && i > 0) {
                if (lists[i] != null) {
                    if (k - lists[i].size() > 0) {
                        resList.addAll(lists[i]);
                        k -= lists[i].size();
                    } else {
                        resList.addAll(lists[i].subList(0, k));
                        k = 0;
                    }
                }
                --i;
            }

            return resList.stream().mapToInt(e -> e).toArray();
        }

        class Pair {
            int key;
            int counts;

            public Pair(int key, int counts) {
                this.key = key;
                this.counts = counts;
            }
        }

        public int[] topKFrequent1(int[] nums, int k) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                int value = map.computeIfAbsent(num, key -> 0);
                map.put(num, ++value);
            }
            Queue<Pair> minHeap = new PriorityQueue<>(k, (p1, p2) -> p1.counts - p2.counts);

            map.forEach((key, value) -> {
                if (minHeap.size() < k) {
                    minHeap.offer(new Pair(key, value));
                } else if (minHeap.peek().counts < value) {
                    minHeap.poll();
                    minHeap.offer(new Pair(key, value));
                }
            });

            int[] res = new int[k];
            for (int i = 0; i < res.length; i++) {
                res[i] = minHeap.poll().key;
            }
            return res;
        }

        public int[] topKFrequent(int[] nums, int k) {
            return topKFrequent2(nums, k);
        }
    }
}
